package course.p3_arraysSort.exa05_mergeSort;

import org.junit.Test;

import java.lang.reflect.Array;
import java.util.Arrays;

public class MergeSort {


    /**
     * 合并算法，合并两个已经排好序的数组
     * @param a 目标数组
     * @param left 左边界
     * @param mid 分界位置
     * @param right 右边界
     * @param <T> 类型
     */
    public static <T extends Comparable<T>> void merge(T[] a,int left,int mid,int right) {
        //新建辅助数组
        T[] tmp= (T[]) Array.newInstance(a[0].getClass(),a.length);

        //p1、p2是检测指针，k是存放指针
        int p1 = left,p2 = mid+1,k = left;

        while(p1<=mid && p2<=right){
            if(a[p1].compareTo(a[p2])<=0)
                tmp[k++] = a[p1++];
            else
                tmp[k++] = a[p2++];
        }
        // 如果第一个序列未遍历完，直接将后面所有元素加到合并的序列中
        while(p1<=mid) tmp[k++] = a[p1++];
        // 如果第二个序列未遍历完,直接将后面所有的元素合并辅助数组中
        while(p2<=right) tmp[k++] = a[p2++];

        //复制回原素组
        for (int i = left; i <=right; i++) {
            a[i]=tmp[i];
        }
    }

    /**
     * 归并排序主函数
     * @param a 数组
     * @param start 起始位置
     * @param end 终止位置
     * @param <T> 类型
     * @return
     */
    public static <T extends Comparable<T>> T[] mergeSort(T[] a,int start,int end) {
        if(start<end) {//当子序列中只有一个元素时结束递归
            int mid = (start+end)/2;//划分子序列
            mergeSort(a, start, mid);//对左侧子序列进行递归排序
            mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
            merge(a, start, mid, end);//合并
        }
        return a;
    }

    @Test
    public void mergeSortTest() {
        Integer[] numbs = {878, 299, 299, 36, 381, 777, 26, 387, 358, 592};
        mergeSort(numbs,0,numbs.length-1);
        System.out.println(Arrays.toString(numbs));
    }




}
